package sword.chapter12Sort;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 合并区间
 *
 * 排序
 *
 * @author K
 * @date 2022-01-10 21:38
 */
public class S74Merge {

    public static int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (x, y) -> x[0] - y[0]);
        int i = 0;
        ArrayList<int[]> list = new ArrayList<>();
        while (i < intervals.length) {
            int[] temp = {intervals[i][0], intervals[i][1]};
            int j = i+1;
            while (j < intervals.length && intervals[j][0] <= temp[1]) {
                temp[1] = Math.max(intervals[j][1], temp[1]);
                j++;
            }
            list.add(temp);
            i = j;
        }

        int[][] result = new int[list.size()][];
        return list.toArray(result);
    }

    public static void main(String[] args) {
        int[][] nums = {
                new int[]{1, 3},
                new int[]{4, 5},
                new int[]{8, 10},
                new int[]{2, 6},
                new int[]{9, 12},
                new int[]{15, 18},
        };

        int[][] result = merge(nums);
        System.out.println();
    }
}
